package chap05.sort;

/**
 * Created by root on 2017/7/10.
 */

class Link{
    public long dData;
    public Link next;

    public Link(long dd) {
        dData = dd;
    }
}

class SortedList {
    private Link first;

    public void insert(Link k) {
        Link current = first;
        Link previous = null;
        while (current!=null && k.dData>current.dData) {
            previous = current;
            current = current.next;
        }
        if (previous == null) {
            first = k;
        } else {
            previous.next = k;
        }
        k.next = current;
    }
    public Link remove(){
        Link temp = first;
        first = first.next;
        return temp;
    }
    public SortedList(Link[] linkArr){
        first = null;
        for (int j=0;j<linkArr.length;j++) {
            insert(linkArr[j]);
        }
    }
}

public class ListInsertionSortApp {
    public static void main(String[] args){
        int size = 10;
        Link[] linkArray = new Link[size];
        Link newLink = null;
        for (int j=0; j<size; j++) {
            int n = (int)(Math.random()*99);
            newLink = new Link(n);
            linkArray[j] = newLink;
        }
        System.out.print("Unsorted array: ");
        for (int j=0; j<size; j++) {
            System.out.print(linkArray[j].dData + " ");
        }
        System.out.println();
        SortedList theSortedList = new SortedList(linkArray);
        for (int j=0; j<size; j++) {
           linkArray[j] = theSortedList.remove();
        }
        System.out.print("Sorted array: ");
        for (int j=0; j<size; j++) {
            System.out.print(linkArray[j].dData + " ");
        }
        System.out.println();
    }
}
